package 算法基础模板.chapter_04;

/**
 * 求组合数
 * // c[a][b] 表示从a个苹果中选b个的方案数
 * for (int i = 0; i < N; i ++ )
 *     for (int j = 0; j <= i; j ++ )
 *         if (!j) c[i][j] = 1;
 *         else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
 * @author Summerday
 */
public class C1 {

    final int N = 2010, mod = (int) 1e9;
    int[][] c = new int[N][N];

    void init(){
        for(int i = 0; i< N; i ++){
            for(int j = 0; j <= i; j ++){
                if(j == 0) c[i][j] = 1;
                else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
            }
        }
    }

    public static void main (String[] args) {
        C1 c1 = new C1();
        c1.init();
        System.out.println(c1.c[5][2]);
    }

}
